﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AlgoTest
{
    class MatchingBraces
    {
        /// <summary>
        /// Checks a string to be gracefully braced.
        /// Actually, this is a task for Regex class, but I don't think I was supposed to simply use it :)
        /// </summary>
        /// <param name="s">The string to be checked</param>
        /// <returns>true if the string is OK</returns>
        public bool checkBraces(string s)
        {
            // opening and closing braces are specially arranged in the same order
            const string openingBraces = "({[";
            const string closingBraces = ")}]";

            var bracesStack = new Stack<char>();

            // TODO: try to use pointers - maybe it would be faster...
            foreach (var ch in s)
            {
                int braceIndex = openingBraces.IndexOf(ch); // here IndexOf uses ordinal comparison and is quite fast, as far as I know
                if (braceIndex >= 0)
                {
                    // current char is an opening brace - so pushing a corresponding closing brace to stack
                    bracesStack.Push(closingBraces[braceIndex]);
                }
                else if (closingBraces.IndexOf(ch) >= 0)
                {
                    // current char is a closing brace - so checking if it's the right brace
                    if
                    (
                        (bracesStack.Count == 0)
                        ||
                        (bracesStack.Peek() != ch)
                    )
                        return false;

                    bracesStack.Pop();
                }
            }

            // if any braces left - return false
            return bracesStack.Count == 0;
        }
    }
}
